package 剑指Offer38字符串的排列;

import java.util.HashSet;
import java.util.LinkedList;

/**
 * @author wtcode
 * @date 2021/3/24 - 7:35
 */
public class Main {
    LinkedList<String> res = new LinkedList<>();
    char[] c;

    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    private void dfs(int num) {
        // 如果c已经拼接好数量的字符串
        // num代表char数组的下标
        if(num == c.length - 1){
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = num ; i < c.length ; i++){
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i,num);
            dfs(num+1);
            swap(i,num);
        }
    }

    private void swap(int a , int b){
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}
